#include <bits/stdc++.h>
using namespace std;
#define int long long

int n, m, fa[100003], w[3003][3003];
vector<array<int, 3>> edges;
set<pair<int, int>> s;

int get_fa(int i) {
	if (fa[i] == i) return i;
	return fa[i] = get_fa(fa[i]);
}

void solve() {
	cin >> n >> m;
	if (m == 0) {
		cout << n - 1 << "\n";
	} else if (n <= 3000) {
		for (int i = 1; i <= n; ++i)
			for (int j = 1; j <= n; ++j) w[i][j] = -1;
		for (int i = 1; i <= n; ++i) fa[i] = i;
		while (m--) {
			int u, v, k;
			cin >> u >> v >> k;
			if (u > v) swap(u, v);
			w[u][v] = k;
		}
		edges.clear();
		for (int i = 1; i <= n; ++i) {
			for (int j = i + 1; j <= n; ++j) {
				if (w[i][j] == -1) w[i][j] = j - i;
				edges.push_back({w[i][j], i, j});
			}
		}
		sort(edges.begin(), edges.end());
		int ans = 0;
		for (auto i : edges) {
			if (get_fa(i[1]) != get_fa(i[2])) {
				fa[get_fa(i[1])] = get_fa(i[2]);
				ans += i[0];
			}
		}
		cout << ans << "\n";
	} else {
		for (int i = 1; i <= n; ++i) fa[i] = i;
		edges.clear(); s.clear();
		while (m--) {
			int u, v, k;
			cin >> u >> v >> k;
			if (u > v) swap(u, v);
			s.insert({u, v});
			edges.push_back({k, u, v});
		}
		for (int i = 1; i <= n; ++i) {
			for (int j = i + 1; j <= n && j - i + 1 <= 10; ++j) {
				if (s.find({i, j}) == s.end()) {
					edges.push_back({j - i, i, j});
				}
			}
		}
		sort(edges.begin(), edges.end());
		int ans = 0;
		for (auto i : edges) {
			if (get_fa(i[1]) != get_fa(i[2])) {
				fa[get_fa(i[1])] = get_fa(i[2]);
				ans += i[0];
			}
		}
		cout << ans << "\n";
	}
}

signed main() {
	freopen("up.in", "r", stdin);
	freopen("up.out", "w", stdout);
	ios::sync_with_stdio(0); cin.tie(0);
	int tc; cin >> tc; while (tc--) solve();
	return 0;
}
